#include <bits/stdc++.h>

using namespace std;

class Node
{
public:
    int val;
    vector<Node *> children;

    Node() {}

    Node(int _val)
    {
        val = _val;
    }

    Node(int _val, vector<Node *> _children)
    {
        val = _val;
        children = _children;
    }
};

class Solution
{
public:
    void preorder(Node *root, vector<int> &res)
    {
        if (root == nullptr)
        {
            return;
        }
        res.push_back(root->val);
        int length = root->children.size();
        for (int i = 0; i < length; i++)
        {
            preorder(root->children[i], res);
        }
    }

    vector<int> preorder(Node *root)
    {
        vector<int> res;
        preorder(root, res);
        return res;
    }
};

int main()
{
    Node *root = new Node(1);
    root->children.push_back(new Node(3));
    root->children.push_back(new Node(4));
    root->children.push_back(new Node(5));
    root->children[0]->children.push_back(new Node(5));
    root->children[0]->children.push_back(new Node(6));
    Solution sol;
    vector<int> res = sol.preorder(root);
    for (auto num : res)
    {
        cout << num << " ";
    }
    cout << endl;
}
